Many data query operations employ some type of sorting operation. Sorting is the process of arranging items in a specific order. The items may have an associated key value that is used in the sorting operation. The sorting objective is to determine a permutation of records that puts the keys in the specified order, e.g., non-decreasing. A sorting operation is characterized by the manner by which the sorting, or rearrangement is accomplished, as well as whether the rearrangement can be accomplished entirely within a single layer of memory (e.g., the internal memory local to the processor executing the sorting operation).
A distribution sort separates records into contiguous ranges so that all records in a range have keys that are less in value than the keys of the records in the next range. A merge sort combines two or more linearly-ordered lists such that the combined list also is linearly ordered.
In some situations, internal memory capacity may not be sufficient to accommodate the sorting operation, and additional operations are required. An external sort refers to a sorting technique applicable to situations in which the records to be sorted exceed the processor's internal memory and another layer of memory may be required. In an external merge-sort, parts of a file are read into the internal memory, ordered (sorted), then rewritten to an external or secondary storage, and finally merged.